package com.atguigu.Greedy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

/**
 * @author tbwtbw
 * @create 2021-11-26 10:25
 */
public class GreedyAlgorithm {
    public static void main(String[] args) {
//创建广播电台,放入到Map
        HashMap<String,HashSet<String>> broadcasts = new HashMap<String, HashSet<String>>();
        //将各个电台放入到broadcasts
        HashSet<String> hashSet1 = new HashSet<String>();
        hashSet1.add("北京");
        hashSet1.add("上海");
        hashSet1.add("天津");

        HashSet<String> hashSet2 = new HashSet<String>();
        hashSet2.add("广州");
        hashSet2.add("北京");
        hashSet2.add("深圳");

        HashSet<String> hashSet3 = new HashSet<String>();
        hashSet3.add("成都");
        hashSet3.add("上海");
        hashSet3.add("杭州");


        HashSet<String> hashSet4 = new HashSet<String>();
        hashSet4.add("上海");
        hashSet4.add("天津");

        HashSet<String> hashSet5 = new HashSet<String>();
        hashSet5.add("杭州");
        hashSet5.add("大连");

        //加入到map
        broadcasts.put("K1", hashSet1);
        broadcasts.put("K2", hashSet2);
        broadcasts.put("K3", hashSet3);
        broadcasts.put("K4", hashSet4);
        broadcasts.put("K5", hashSet5);

        //记录没有被覆盖到的城市
        HashSet<String> allareas = new HashSet<>();
        allareas.addAll(hashSet1);
        allareas.addAll(hashSet2);
        allareas.addAll(hashSet3);
        allareas.addAll(hashSet4);
        allareas.addAll(hashSet5);

        ArrayList<String> selects = new ArrayList<>();//记录选择的广播
        String maxkey = null;
        HashSet<String> maxkeySet = new HashSet<>();//记录maxkey能够覆盖allareas中没有被覆盖的城市
        HashSet<String> tempSet = new HashSet<>();//记录某广播能够覆盖allareas中没有被覆盖的城市
        while (allareas.size() > 0){//有没被覆盖到的城市就继续循环
            maxkey = null;//一大轮就得到一个maxkey,然后置空
            for (String key : broadcasts.keySet()){

                tempSet.clear();
                HashSet<String> areas = broadcasts.get(key);//key能覆盖的城市们
                tempSet.addAll(areas);
                tempSet.retainAll(allareas);//求key 能覆盖城市与未覆盖城市的交集

                if (maxkey != null){
                    maxkeySet = broadcasts.get(maxkey);
                    maxkeySet.retainAll(allareas);
                }
                if (tempSet.size() > 0 && (maxkey == null //tempset为空就没必要看了，maxkey也不用改
                        || tempSet.size() > maxkeySet.size()))
                    maxkey = key;
            }

            if (maxkey != null){
                selects.add(maxkey);
                allareas.removeAll(broadcasts.get(maxkey));
            }
        }

        System.out.println(selects);
    }
}
